package com.LeeCode;

/**
 * 和可被 K 整除的子数组
 */

public class Code974 {
    public static void main(String[] args) {
        int[] nums = {4, 5, 0, -2, -3, 1};
        int k = 5;
        System.out.println(new Code974().subarraysDivByK(nums, k));
    }

    public int subarraysDivByK(int[] nums, int k) {
        int[] cnt = new int[k];
        cnt[0] = 1;
        int ans = 0, preSum = 0;
        for (int num : nums) {
            preSum += num;
            int target = preSum % k;
            if (target < 0) target += k;
            ans += cnt[target];
            cnt[target]++;
        }
        return ans;
    }
}
